132

11

Randomness and Complexity

This definition leads to the intuitively unsatisfying consequence that the highest

possible complexity, the least regularity, the greatest potential information gain, etc.

are possessed by a purely random process, which then implies that the output of the

proverbial team of monkeys tapping on keyboards is more complex than a Shake-

speare play (the difference would, however, vanish if the letters of the two texts were

encoded in such a way that the same symbol was used to encode each letter). What we

would like is some quantity that is small for highly regular structures (low disorder),

then increases to a maximum as the system becomes more disordered, and finally

falls back to a low value as the disorder approaches pure randomness.

In order to overcome this difficulty, Gell-Mann has proposed effective complexity

to be proportional to the length of a concise description of a set of an object’s

regularities, which amounts to the algorithmic complexity of the description of the

set of regularities. This prescription certainly fulfils the criterion of correspondence

with the intuitive notion of complexity; both a string consisting of one type of symbol

and the monkey-text would have no variety in their regularity and hence minimal

complexity. One way of assessing the regularities is to divide the object into parts

and examine the mutual algorithmic complexity between the parts. The effective

complexity is then proportional to the length of the description of those regularities.

Correlations within a symbolic sequence (string) have been used by Grassberger

to define effective measure complexity (EMC) from the correlation information

(see Sect. 6.2):

η =

∞

Σ

m=2

(m − 1)km .

(11.27)

In effect, it is a weighted, average correlation length.

A more physically oriented approach has been proposed by Lloyd and Pagels.

Their notion of (thermodynamic) depth attempts to measure the process whereby an

object is constructed. A complex object is one that is difficult to put together; ¹² the

average complexity of a state is the Shannon entropy of the set of trajectories leading

to that state (minus sigma summation p Subscript i Baseline log p Subscript i−^Σ pi log pi, where p Subscript ipi is the probability that the system has arrived at

that state by theiith trajectory), and the depthscript upper DD of a system in a macroscopic statedd

istilde minus log p Subscript i∼−log pi. An advantage of this process-oriented formulation is the way in which

the complexity of copies of an object can be dealt with; the depth of a copy, or any

number of copies, is proportional to the depth of making the original object plus the

depth of the copying process.

Process is used by Lempel and Ziv to derive a complexity measure, called pro-

duction complexity, based on the gradual buildup of new patterns (rate of vocabulary

growth) along a sequence ss:

c(s) = min{cH (s)}

(11.28)

12 Cf. the nursery rhyme Humpty Dumpty sat on a wall/Humpty Dumpty had a great fall/And all the

king’s horses and all the king’s men/Couldn’t put Humpty together again. It follows that Humpty

Dumpty had great depth, hence complexity.